/*
03-树2 List Leaves
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Tree =========================================*/
#define TreeElementType int

typedef struct TreeNode *Tree;
typedef struct TreeNode TreeNode;
struct TreeNode {
    TreeElementType data;
    TreeNode *left;
    TreeNode *right;
};

TreeNode* createTreeNode(TreeElementType data) {
    TreeNode* node = calloc(1, sizeof(TreeNode));
    node->data = data;
    return node;
}

void freeTree(TreeNode* root) {
    if(root->left) {
        freeTree(root->left);
    }
    if(root->right) {
        freeTree(root->right);
    }
    free(root);
}

// 访问树节点时需要完成的操作，一般是输出，
// 这里定义的是函数头，在使用的程序里写具体的实现
void visitTreeNode(TreeNode* node);

/* Queue ====================================*/
#define QueueElementType TreeNode*
typedef struct LinkedNode LinkedNode;
struct LinkedNode {
    QueueElementType data;
    LinkedNode* next;
};

typedef struct Queue Queue;
struct Queue {
    int size;
    // 队列的头尾节点
    LinkedNode* first;
    LinkedNode* last;
};

Queue* createQueue() {
    Queue* queue = (Queue*) malloc(sizeof(Queue));
    queue->first = queue->last = NULL;
    queue->size = 0;
    return queue;
}

int isEmptyQueue(Queue *queue) {
    return queue->first == NULL;
}

void enQueue(Queue *queue, QueueElementType data) {
    LinkedNode* node = (LinkedNode*)malloc(sizeof(LinkedNode));
    queue->size++;
    node->data = data;
    node->next = NULL;
    if (queue->first == NULL) {
        queue->first = queue->last = node;
        return;
    }
    queue->last->next = node;
    queue->last = node;
}

QueueElementType deQueue(Queue* queue) {
    // 取数据
    LinkedNode* node = queue->first;
    QueueElementType data = node->data;
    // 移动头指针
    queue->first = node->next;
    queue->size--;
    // 释放内存
    free(node);
    
    return data;
}

/* Tree-Traversal-Level ================================*/
void LevelTraversal(Tree root) {
    if (root == NULL) {
        return;
    }
    int isp = 0;
    Queue* queue = createQueue();
    enQueue(queue, root);
    while (!isEmptyQueue(queue)) {
        TreeNode* tn = deQueue(queue);
        visitTreeNode(tn);
        if (tn->left != NULL) {
            enQueue(queue, tn->left);
        }
        if (tn->right != NULL) {
            enQueue(queue, tn->right);
        }
    }
    free(queue);
}

/* current ===============================*/
int isp = 0;
void visitTreeNode(TreeNode* node) {
    // printf("%d ", node->data);
    if (node->left == NULL && node->right == NULL) {
        if (isp) {
            printf(" ");
        }
        printf("%d", node->data);
        isp = 1;
    }
}

Tree read(TreeNode* nodes) {
    int n;
    scanf("%d", &n);
    // 是否叶子节点
    int *isLeave = (int*) malloc(sizeof(int)*n);
    memset(isLeave, 0, sizeof(int)*n);
    for (int i=0; i<n; i++) {
        char slidx[5], sridx[5];
        scanf("%s %s", slidx, sridx);
        char lidx = slidx[0];
        char ridx = sridx[0];
        nodes[i].data = i;
        // printf("%d) %d %s %s\n", i, nodes[i].data, lidx, ridx);
        if (lidx == '-') {
            nodes[i].left = NULL;
        } else {
            nodes[i].left = &nodes[lidx-'0'];
            isLeave[lidx-'0'] = 1;
        }
        if (ridx == '-') {
            nodes[i].right = NULL;
        } else {
            nodes[i].right = &nodes[ridx-'0'];
            isLeave[ridx-'0'] = 1;
        }
    }
    Tree root = NULL;
    for (int i=0 ;i<n; i++) {
        if (!isLeave[i]) {
            root = &nodes[i];
            break;
        }
    }
    free(isLeave);
    return root;
}

#define MAX_SIZE 10
int main() {
    // 预先分配t1, t2的内存空间
    TreeNode t1nodes[MAX_SIZE];
    Tree tree = read(t1nodes);
    // preorderTraversal(tree);
    // printf("\n");
    LevelTraversal(tree);
    printf("\n");
    return 0;
}
